The present invention relates generally to network systems. More particularly, the invention relates to a traffic conditioning marker associated with a router.
With the explosive growth of the internet, there is a growing interest in using the internet and other internet protocol-based networks to deliver high bandwidth selections such as multi-media video and audio material. The internet is a connectionless network offering best effort delivery service. Packets of data are routed to an address of an intended recipient whose address is contained in the packet. A specific connection between the sender and the intended recipient is not required because all host nodes on the network include the inherent capability to route packets from node to node until delivery occurs.
The packet delivery scheme is constructed as a best effort delivery system in which the delivery of packets is not guaranteed. Packets may be sent via different routes in an effort to increase the likelihood of delivery. Thus, if one node on the network is experiencing congestion, subsequent packets may be alternatively routed to avoid the congested node. This means that packets do not inherently have a guaranteed arrival time. In other words, packets corresponding to a single message may be received out of order.
Multi-media data often requires real-time delivery. In the case of audio or video data, the data stream representing a particular media selection needs to be delivered in the proper time sequence to allow the user to play back the audio or video selection xe2x80x9clivexe2x80x9d as it is being sent.
In the best effort service model, the network allocates the bandwidth among all of the contending users as best as it can. The network attempts to serve all of the users without making any commitment to data delivery rates or any other service quality. As multi-media and real-time applications proliferate, it is becoming more desirable to provide service guarantees for internet delivery. Many enterprises and users are willing to pay an additional price to get preferred service from the internet provider.
The integrated services model and the differentiated services model have been proposed to provide guaranteed service. The integrated services model is analogous to the circuit-switched service in the current telephone system. While the integrated services model provides guaranteed service, it has two major drawbacks. First, the amount of state information increases proportionately with the increased flow of data which leads to poor scalability at the core routers. Second, implementation of the integrated services model requires significant changes to the internet infrastructure and, therefore, requires significant expenditures of capital. For these reasons, the integrated services model is not an economically or logistically feasible approach at this time.
The differentiated services model provides a simple and predefined per-hop behavior (PHB) level service differentiation in the internet core routers. Per-flow or flow aggregate marking, shaping and policing are performed at the edge routers. The differentiated services model does not suffer from the scalability problems associated with the integrated services model. The differentiated services model also requires far less significant changes to the existing internet infrastructure.
Referring to FIG. 1, a prior art networking system 10 employing the differentiated services model is illustrated and includes a first domain 12 and a second domain 14. The first and second domains 12 and 14 each include multiple core routers 16, 18, 20, 22, 24 and 26 that are connected by backbone networks 30 and 32. The first domain 12 and the second domain 14 are interconnected to each other through edge routers 36 and 38. End users 40, 42, 44, 46, 48, and 50 are likewise connected through edge routers 52, 54, 56, and 58 by stub domain 60 and 62.
Before entering a differentiated services domain, such as the first domain 12, a packet is assigned a differentiated services code point (DSCP) by a traffic conditioning marker associated with edge router 52. When the packet reaches a differentiated services aware router such as the core router 18, the DSCP contained in the packet is checked to determine a forwarding priority of the packet.
The DSCP contained in the packet may be changed when it crosses a boundary of two domains. For example, in FIG. 1 a packet is sent by one of the end users 40, 42, 44 associated with host 60 to one of the end users 46, 48, or 50 associated with stub domain 62. The packet may be marked by the edge router 52 or by another marker associated with the stub domain 60 as a high priority DSCP packet when the packet enters the first domain 12.
At a boundary 64 between the first domain 12 and the second domain 14, the marker at the edge router 38 may remark the packet as a low priority DSCP packet before forwarding the packet to the second domain 14 if the first domain 12 has not negotiated enough traffic forwarding rate with the second domain 14 for the requested priority level.
Currently, a single class for expedited forwarding (EF) and four classes for assured forwarding (AF) have been defined. EF was originally proposed to be used for premium services. After EF and AF were defined, it was expected that premium services traffic would be allocated only a small percentage of network capacity and would be assigned to a high-priority queue in the routers. EF is ideal for real-time services such as internet protocol (IP) telephony, video conferences, and other real time multi-media applications.
AF is used for assured services. The Red-In/Out (RIO) approach was proposed to ensure that the expected capacity specified by a traffic profile is obtained. Upon the arrival of each packet, the packet is marked as xe2x80x9cInxe2x80x9d or xe2x80x9cOutxe2x80x9d depending upon whether the packet is within the traffic profile. When a differentiated services-aware router is employed, all of the incoming packets are queued in the original transmission order. During network congestion, however, the router drops the packets that are marked as xe2x80x9cOutxe2x80x9d. If the network controls the aggregate xe2x80x9cInxe2x80x9d packets such that they do not exceed the capacity of the link, the throughput of each flow or flow aggregate can be assured to be at least the rate defined in the traffic profile.
To ensure service differentiation, Assured Forwarding Per-Hop Behavior (AFPHB) specifies four traffic classes with three drop precedence levels within each class. In all, there are 12 DSCP""s for AFPHB. Within an AF class, a packet is marked as one of three colors, green, yellow or red. Green has the lowest drop probability and red has the highest drop probability.
An internet connection typically spans a path involving one or more network domains as is illustrated in FIG. 1. If a guaranteed arrival is desired, the network system 10 must ensure that the aggregate traffic along the path does not exceed any of the inter-domain negotiated traffic rates. This is very difficult since the inter-domain service agreements are not usually renegotiated at the initiation of each new connection. For AF, the inter-domain traffic rates are usually negotiated statically and/or updated periodically to avoid signaling overhead and scalability problems. The negotiation is usually based on statistical estimation. At any given time, the aggregate flow rate may be higher or lower than the negotiated rate.
Referring now to FIG. 2, a traffic conditioning marker 68 that is typically located in an edge router between an upstream domain 70 and a downstream domain 72 is illustrated and includes a packet classifier 76 which separates xe2x80x9cInxe2x80x9d packets from xe2x80x9cOutxe2x80x9d packets. A rate generator 78 defines a negotiated token rate of r bits per second. A packet remarker 80 determines whether to remark some of the xe2x80x9cInxe2x80x9d packets as xe2x80x9cOutxe2x80x9d packets depending upon a maximum burst rate b, the incoming flow rate of xe2x80x9cInxe2x80x9d packets, and the negotiated rate between the upstream and the downstream domain 70 and 72. A forwarding engine 82 sends the xe2x80x9cOutxe2x80x9d packets forwarded by the packet classifier 76 to the downstream domain 72. The forwarding engine 82 transmits xe2x80x9cInxe2x80x9d and xe2x80x9cOutxe2x80x9d packets passed by the packet remarker 80 to the downstream domain 72.
Referring to FIG. 3, the operation of the packet remarker 80 is illustrated in further detail. The rate generator 78 feeds the packet remarker 80 tokens at a constant of r tokens or bits per second as is illustrated at 90 in FIG. 3. When a packet marked as xe2x80x9cInxe2x80x9d arrives from upstream domain 70, packet remarker 80 checks to see whether there are enough tokens for the packet. If enough tokens are available, the packet is forwarded as xe2x80x9cInxe2x80x9d and the tokens are deducted. If there are an insufficient number of tokens, the xe2x80x9cInxe2x80x9d packet is demoted to xe2x80x9cOutxe2x80x9d and forwarded to the downstream domain 72.
When the aggregate traffic of certain service levels exceeds the negotiated rate defined in the traffic profile, the packet is demoted to a lower service level. If the traffic rate of the service level is lower than the rate defined in the traffic profile, the lower service level packets are not promoted to a higher level because of problems associated with identifying which packets to promote.
For example, a first flow subscribes for certain throughput of assured services and a second flow subscribes for best effort services. Both packets pass through several domains. Some of the xe2x80x9cInxe2x80x9d packets of the first flow are demoted while crossing one of the domains if the traffic controller of a downstream domain has extra xe2x80x9cInxe2x80x9d tokens available, and if promotions are allowed at the downstream domain, both the best effort traffic and the demoted assured services traffic compete for promotion. The demoted assured services packets of the first flow should be promoted first. Because there is no way to identify demoted assured services packets, selective promotion cannot occur. Randomly promoting packets from both flows does not increase the likelihood that assured services of the first flow will occur.
In the network system according to the invention, packets that were originally marked as xe2x80x9cInxe2x80x9d and were subsequently marked as xe2x80x9cOutxe2x80x9d packets at nodes where the aggregate incoming traffic rate exceeded the available band-width are subsequently remarked as xe2x80x9cInxe2x80x9d packets when the bandwidth at a subsequent node is sufficient. According to the invention, the demoted xe2x80x9cInxe2x80x9d packets are identifiable from xe2x80x9cOutxe2x80x9d packets that were originally xe2x80x9cOutxe2x80x9d. In addition, the networking system according to the invention ensures that promotion of the packets is fair relative to the respective flow traffic rate. The fairness is achieved by randomly making marking decisions on the packets. The traffic controller, according to the present invention, employs the AFPHB specified packet markings.
To support this functionality, a three-color marking process is employed with the colors red, yellow, and green. Yellow is used as an indicator for temporary demotion. The marking scheme of the traffic controller, according to the invention, is fair in demoting and promoting packets and provides improved performance for the in-profile traffic as compared to conventional schemes discussed above.
For a more complete understanding of the invention, its objects and advantages, reference may be had to the following specifications and to the accompanying drawings.